/*
 * @lc app=leetcode.cn id=552 lang=typescript
 *
 * [552] 学生出勤记录 II
 */

// @lc code=start
function checkRecord(n: number): number {
  // dp[i][j][k],[0,i]字串，j个'A',k个'L‘情况下的出勤记录
  const dp = new Array(n + 1)
    .fill(0)
    .map((_) => new Array(2).fill(0).map((_) => new Array(3).fill(0)));
  const mod = 10 ** 9 + 7;

  dp[0][0][0] = 1;
  for (let i = 1; i <= n; i++) {
    // 'A'结尾的出勤记录
    for (let k = 0; k <= 2; k++) {
      dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
    }
    // 'L'结尾的出勤记录
    for (let j = 0; j <= 1; j++) {
      for (let k = 1; k <= 2; k++) {
        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
      }
    }
    // 'P'结尾的出勤记录
    for (let j = 0; j <= 1; j++) {
      for (let k = 0; k <= 2; k++) {
        dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % mod;
      }
    }
  }

  let res = 0;
  for (let j = 0; j <= 1; j++) {
    for (let k = 0; k <= 2; k++) {
      res = (res + dp[n][j][k]) % mod;
    }
  }
  return res;
}
// @lc code=end
